/*
Maximum Subarray


Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

编程之美

*/
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
//#include <cstdio>

using namespace std;



class Solution1 {
	
public:
    int maxSubArray(vector<int>& nums) {

		int maxinum = 0;
		int sum = 0;

		for (size_t i = 0; i < nums.size(); i++)
		{
			for (size_t j = i; j < nums.size(); j++)
			{
				for (size_t k = i; k <= j; k++)
				{
					sum += nums[k];
				}
				if (sum > maxinum)
				{
					maxinum = sum;
				}
				sum = 0;
			}

		}
		return maxinum;
        
    }
};


class Solution2 {
	/*DP*/
public:
	int maxSubArray(vector<int>& nums) {

		int size = nums.size();
		vector<int> all(size, 0);
		vector<int> start(size, 0);

		start[size - 1] = nums[size - 1];
		all[size - 1] = nums[size - 1];

		for (int i = size - 2; i >= 0; i--)
		{
			start[i] = max(nums[i], nums[i] + start[i+1]);
			all[i] = max(start[i],  all[i + 1]);
		}
		return all[0];
	}
};


class Solution3 {
	/*DP*/
public:
	int maxSubArray(vector<int>& nums) {

		int size = nums.size();
		int start;
		int all;
		start = nums[size - 1];
		all = nums[size - 1];

		for (int i = size - 2; i >= 0; i--)
		{
			start = max(nums[i], nums[i] + start);
			all = max(start, all);
		}
		return all;
	}
};

class Solution {
	
public:
	int maxSubArray(vector<int>& nums) {

		if (nums.size()<=0)
		{
			return 0;
		}

		int size = nums.size();
		int sum = 0;
		int max = nums[0];
		
		for (int i = 0; i < size; i++)
		{
			if (sum>=0)
			{
				sum += nums[i];
			}
			else
			{
				sum = nums[i];
			}

			if (sum>max)
			{
				max = sum;
			}
		}
		return max;
	}
};


int main(int argc, char* argv[])
{
	cout<<"Max Subarray"<<endl;
	
	cout<<"Input n"<<endl;
	
	
	int n;
	vector<int> nums;
	freopen("testData.txt","r",stdin);
	while (cin >> n)
	{
		cout << n << endl;
		nums.push_back(n);


	}

	int sum;
	Solution s;
	sum = s.maxSubArray(nums);
	cout << "The sum of subarray"<<sum<< endl;

	system("pause");

	
/*
	while(n)
	{
		int i;
		cin>>i;
		nums.push_back(i);
		n--;
	}
		
	cout<<"Input nums"<<endl;
	
	for(int i = 0; i < nums.size();i++)
	{
		cout<<nums[i]<<" ";
	}
	cout<<endl;
	
	Solution s;
	*/
	//result = s.pow(x,n);
	
	//cout<<"The result of ("<<x<<","<<n<<") is : " <<result<<endl;
	
	//fclose(stdin);
	
	return 0;
}